#include <stdio.h>

int Max3(int A , int B , int C );
int MaxSum(int a[], int left, int right);
int MaxSubseqSum3(int List[], int N );

int main(void)
{
	int list[] = {4,-3,5,-2,-1,2,6,-2};
	MaxSubseqSum3(list,8);
	printf("最大子列和= %d",MaxSubseqSum3(list,8));

}

int MaxSum(int a[], int left, int right){
	int leftmaxsum , rightmaxsum;/*求和临时数组  左边求和 右边求和    */
	int leftbordersum , rightbordersum;/*存放跨越边界的最大值 */

	int maxleft , maxright;/*存放左右问题的解 */
	int center ;
	int i,j;	

	if(left == right){/*递归结束条件 */
		if(a[left]>0) return a[left];
		else return 0;
	}

	center = (right + left) / 2;/*找到中分点 */

	/*递归求得两边最大子列合*/
	maxleft = MaxSum(a , left , center);
	maxright = MaxSum(a,center + 1, right);
	/*求跨越分界线的最大子列和*/
	leftmaxsum = 0; leftbordersum = 0;
	for(i = center ; i >= left ; i--){/*向左扫描*/
		leftmaxsum += a[i];/*累加*/
		if(leftmaxsum>leftbordersum)/*保存最大值*/
			leftbordersum = leftmaxsum;
	}

	rightmaxsum = 0; rightbordersum = 0;
	for(i = center + 1; i <= right ; i++){/*向右扫描*/
		rightmaxsum += a[i];
		if(rightmaxsum > rightbordersum)
			rightbordersum = rightmaxsum;
	printf("center=%d\n leftmaxsum=%d \n rightmaxsum=%d \n leftbordersum=%d \n righrbordersum=%d\n",center,leftmaxsum,rightmaxsum,leftbordersum,rightbordersum);
	}
		
	j = Max3(maxleft,maxright,leftbordersum + rightbordersum);
	printf("maxlun=%d\n\n",j);
	return j;
}

int Max3(int A , int B , int C ){/*求三个数的最大的一个*/
	 return A>B ? A>C ? A : C : B>C ? B : C; 
}

int MaxSubseqSum3(int List[], int N){/*封装统一入口*/
	return MaxSum(List,0,N-1);

}
